package algorithm;

import java.util.Arrays;

/**
 * @author: vince_zww
 * @date: 2019/9/8 10:13
 * @desceription: 归并排序
 */
public class MergeSort {

    public static void main(String[] args) {
        int a[] = {99,9,6,8,10,2,5,3,4,7,12,15,48,78,95,35,23,29,98,19};

        long mergeSortStartTime = System.nanoTime();
        System.out.println(Arrays.toString(mergeSort(a)));
        long mergeSortEndTime = System.nanoTime();
        System.out.println("归并排序运行时间："+(mergeSortEndTime-mergeSortStartTime)+"ns");

    }

    /**
     * 归并排序
     */
    private static int[] mergeSort(int[] a){
        //拷贝，不改变参数
        int[] arr = Arrays.copyOf(a,a.length);

        if(arr.length<2){
            return arr;
        }
        //从中间拆分成2个数组
        int middle = (int) Math.floor(arr.length/2);
        int[] left = Arrays.copyOfRange(arr,0,middle);
        int[] right = Arrays.copyOfRange(arr,middle,arr.length);

        return merge2(mergeSort(left),mergeSort(right));
    }

    private static int[] merge(int[] left,int[] right){
        int[] result = new int[left.length+right.length];
        int i = 0;
        while (left.length>0 && right.length>0){
            if (left[0]<=right[0]){
                result[i++] = left[0];
                left = Arrays.copyOfRange(left,1,left.length);
            }else {
                result[i++] = right[0];
                right = Arrays.copyOfRange(right,1,right.length);
            }
        }
        while (left.length>0){
            result[i++] = left[0];
            left = Arrays.copyOfRange(left,1,left.length);
        }
        while (right.length>0){
            result[i++] = right[0];
            right = Arrays.copyOfRange(right,1,right.length);
        }

        return result;
    }

    //第二种写法，更优；节约了重新复制数组的步骤
    private static int[] merge2(int[] left,int[] right){
        int[] result = new int[left.length + right.length];
        for (int index =0,i = 0,j = 0; index < result.length; index++) {
            if(i >= left.length){
                result[index] = right[j++];
            }else if(j >= right.length){
                result[index] = left[i++];
            }else if(left[i] > right[j]){
                result[index] = right[j++];
            }else {
                result[index] = left[i++];
            }
        }
        return result;
    }

}
